|
; k = 0, \ldots, n\} | properties = Symmetric Distance regular Unit distance Hamiltonian Bipartite | notation = ''Qn'' }} In graph theory, the hypercube graph ''Qn'' is a regular graph with 2''n'' vertices, 2''n''−1''n'' edges, and ''n'' edges touching each vertex. It can be obtained as the one-dimensional skeleton of the geometric hypercube; for instance, ''Q''3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Alternatively, it can be obtained from the family of subsets of a set with ''n'' elements, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single element. Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube, ''Q''''n'' that is a cubic graph is the cubical graph, ''Q''3. == Construction == The hypercube graph ''Q''''n'' may be constructed from the family of subsets of a set with ''n'' elements, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single element. Equivalently, it may be constructed using 2''n'' vertices labeled with ''n''-bit binary numbers and connecting two vertices by an edge whenever the Hamming distance of their labels is 1. These two constructions are closely related: a binary number may be interpreted as a set (the set of positions where it has a 1 digit), and two such sets differ in a single element whenever the corresponding two binary numbers have Hamming distance 1. Alternatively, ''Q''n+1 may be constructed from the disjoint union of two hypercubes ''Q''n, by adding an edge from each vertex in one copy of ''Q''n to the corresponding vertex in the other copy, as shown in the figure. The joining edges form a perfect matching. Another definition of ''Q''''n'' is the Cartesian product of ''n'' two-vertex complete graphs ''K''2. More generally the Cartesian product of copies of a complete graph is called a Hamming graph; the hypercube graphs are examples of Hamming graphs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hypercube graph」の詳細全文を読む スポンサード リンク
|